﻿using System;
using System.Collections.Generic;
using System.Text;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0044_UpdateMatrix : IAlgorithm
    {
        // 542. 01 矩阵

        // 给定一个由 0 和 1 组成的矩阵 mat ，请输出一个大小相同的矩阵，其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。
        // 两个相邻元素间的距离为 1 。

        // 提示：
        //  m == mat.length
        //  n == mat[i].length
        //  1 <= m, n <= 10^4
        //  1 <= m* n <= 10^4
        //  mat[i][j] is either 0 or 1.
        //  mat 中至少有一个 0 

        public void Test()
        {
            // 算法参数定义

            // 算法执行与打印
            //Console.WriteLine(UpdateMatrix());
        }

        // 算法
        // BFS，记住模版要点，找起始点，分层进队，若需要知道层数则每层开始记录size
        public int[][] UpdateMatrix(int[][] mat)
        {
            var queue = new Queue<int[]>();
            for (int i = 0; i < mat.Length; i++)

                for (int j = 0; j < mat[0].Length; j++)
                    if (mat[i][j] == 0)
                        queue.Enqueue(new int[] { i, j });
                    else
                        mat[i][j] = -1;
            int[] directions = { -1, 0, 1, 0, -1 };
            int step = 1;
            while (queue.Count > 0)
            {
                int size = queue.Count;
                for (int i = 0; i < size; i++)
                {
                    var tempPoint = queue.Dequeue();
                    for (int j = 0; j < directions.Length - 1; j++)
                    {
                        int x = tempPoint[0] + directions[j];
                        int y = tempPoint[1] + directions[j + 1];
                        if (x < 0 || x >= mat.Length || y < 0 || y >= mat[0].Length || mat[x][y] >= 0)
                            continue;
                        mat[x][y] = step;
                        queue.Enqueue(new int[] { x, y });
                    }
                }
                step++;
            }
            return mat;
        }
    }
}
